package node;

import sun.reflect.generics.tree.Tree;

import java.util.*;

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }

    public boolean isSymmetric(TreeNode root) {
        return isSame(root.left,root.right);
    }

    public static boolean isSame(TreeNode left,TreeNode right){
        if(left==null && right==null){
            return true;
        }
        if(left!=null || right!=null){
            return false;
        }
        if(left.val==right.val && isSame(right.right,left.left) && isSame(right.left,left.right)){
            return true;
        }
        return false;
    }

    //判断二叉树是否存在某个指定值得路径
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null){
            return false;
        }
        return hasPathSum1(root,sum);
    }
    public boolean hasPathSum1(TreeNode root, int sum) {
        if(root.left==null &&root.right==null && sum-root.val ==0){
            return true;
        }
        if(root.left==null &&root.right==null && sum-root.val !=0){
            return false;
        }
        boolean left =false;
        boolean right = false;
        if(root.left!=null){
            left = hasPathSum1(root.left,sum-root.val);
        }
        if(root.right!=null){
            right = hasPathSum1(root.right,sum-root.val);
        }
        return left || right;

    }


    //序列化二叉树
    String Serialize(TreeNode root) {
        if(root==null){
            return "#!";
        }
        StringBuilder sb=new StringBuilder();
        Serialize2(root,sb);
        return sb.toString();
    }
    void Serialize2(TreeNode root,StringBuilder sb){//前序遍历
        if(root==null){
            sb.append("#!");
            return;
        }
        sb.append(root.val);
        sb.append("!");
        Serialize2(root.left,sb);
        Serialize2(root.right,sb);
    }


    //反序列化
    TreeNode Deserialize(String str) {
        if(str.length()==0)return null;
        String[] strs=str.split("!");
        return Deserialize2(strs);

    }
    int index=-1;

    TreeNode Deserialize2(String[] strs){
        index++;
        if(!strs[index].equals("#")){
            TreeNode root=new TreeNode(0);
            root.val=Integer.parseInt(strs[index]);
            root.left=Deserialize2(strs);
            root.right=Deserialize2(strs);
            return root;
        }
        return null;
    }

    //按之字形打印二叉树
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> >   res = new ArrayList<>();
        if (pRoot==null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        int a=1;
        while (queue.size()>0){
            int len = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            while (len>0){
                TreeNode t = queue.poll();
                list.add(t.val);
                if (t.right!=null){
                    queue.add(t.right);
                }
                if (t.left!=null){
                    queue.add(t.left);
                }
                len--;
            }
            if (a%2==1){
                //反转
                ArrayList<Integer> rever  = new ArrayList<>();
                for (int x=list.size()-1;x>-1;x--){
                    rever.add(list.get(x));
                }
                list = rever;
            }
            res.add(list);
            a++;
        }
        return res;
    }


    //判断一棵树是否是平衡二叉树/左右高度差小于等于1  且左右子树同样平衡
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root==null){
            return false;
        }
        return getDeptByNode(root) == -1?false:true;
    }

    public static int getDeptByNode(TreeNode root){
        if (root==null){
            return 0;
        }
        int left = getDeptByNode(root.left);
        int right = getDeptByNode(root.right);
        if (left==-1 || right==-1 ||Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left,right)+1;
    }




    /*
    * 输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。
    * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
    * */
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> res = FindPath(root,target,1);
        for (int a=0;a<res.size();a++){
            ArrayList<Integer> t = res.get(a);
            for (int x:t) {
                t.remove(x);
                t.add(x);
            }
        }
        return res;
    }
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target,int no) {
        ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
        if (root.left == null && root.right==null && target - root.val!=0){
            return arr;
        }
        if (root.left == null && root.right==null && target - root.val==0){
            ArrayList<Integer> arr1= new ArrayList<>();
            arr1.add(root.val);
            arr.add(arr1);
            return arr;
        }
        ArrayList<ArrayList<Integer>> left=FindPath(root.left,target-root.val);
        ArrayList<ArrayList<Integer>> right=FindPath(root.right,target-root.val);
        for (int a=0;a<left.size();a++){
            left.get(a).add(root.val);
            arr.add(left.get(a));
        }
        for (int b=0;b<right.size();b++){
            right.get(b).add(root.val);
            arr.add(right.get(b));
        }
        return arr;
    }

    //判断一颗二叉树是否对称
    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null){
            return true;
        }
        return isSym(pRoot.left,pRoot.right);
    }

    //从上往下打印出二叉树的每个节点，同层节点从左至右打印。
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<>();
        if(root==null){
            return res;
        }
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode head = queue.poll();
            if (head.left!=null){
                queue.add(head.left);
            }
            if (head.right!=null){
                queue.add(head.right);
            }
            res.add(head.val);
        }
        return res;
    }


    /*
    * 判断树root2是否是root1的子树(请注意 子树和子结构是两个概念)
    * */
    public static boolean HasSubtrees(TreeNode root1,TreeNode root2) {
        if (root1== null && root2==null){   //两个都为空
            return true;
        }
        if (root1!= null && root2==null){   //大树这个地方不为空 但是子树为空
            return true;
        }
        if (root1== null && root2!=null){
            return false;
        }
        //头节点值不相同  或者左右子树其中一个不相同
        if (root1.val !=root2.val || (!HasSubtrees(root1.left,root2.left) || !HasSubtrees(root1.right,root2.right))){
            return HasSubtrees(root1.left,root2) || HasSubtrees(root1.right,root2);
        }
        //头节点值相同且左右子树都相同
        if (root1.val==root2.val && HasSubtrees(root1.left,root2.left) && HasSubtrees(root1.right,root2.right)){
            return true;
        }
        return false;
    }

    static boolean isSym(TreeNode p1,TreeNode p2){
        if (p1 ==null && p2 == null){
            return true;
        }
        if (p1 !=null && p2 == null){
            return false;
        }
        if (p1 ==null && p2 != null){
            return false;
        }
        if (p1.val == p2.val && isSym(p1.left,p2.right) && isSym(p1.right,p2.left)){
            return true;
        }
        return false;
    }

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //先反转链表
        ListNode next = null;
        ListNode pre = null;
        while (listNode!=null){
            next = listNode.next;
            listNode.next = pre;
            pre= listNode;
            listNode = next;
        }
        ArrayList<Integer> alist=new ArrayList<Integer>();
        while(listNode!=null){
            alist.add(listNode.val);
            listNode = listNode.next;
        }
        return alist;

    }
    /*
    * 通过二叉树的前序  中序  重建一个二叉树
    * */
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return reConstructBinaryTree(pre,in,0,pre.length-1);

    }
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in,int begin,int end) {   //这里的begin和end是以中序划分出来的小规模
        if (begin > end){
            return null;
        }
        int headIndex = getHeadIndex(pre,in,begin,end);
        TreeNode root = new TreeNode(pre[headIndex]);
        if (begin == end){
            return root;
        }
        int index = getIndex(pre[headIndex],in);   //获得根节点在中序中的位置
        root.left = reConstructBinaryTree(pre,in,begin,index-1);
        System.out.println("左边完事"+"headIndex:"+headIndex+"   begin:"+begin +"   end:"+end+ "  index:" +index);
        root.right = reConstructBinaryTree(pre,in,index+1,end);
        System.out.println("右边完事"+"headIndex:"+headIndex+"   begin:"+begin +"   end:"+end+ "  index:" +index);
        return root;
    }

    public static int getIndex(int n,int[] arr){
        for (int a = 0;a<arr.length;a++){
            if (arr[a] == n){
                return   a;
            }
        }
        return 0;
    }
    //中序begin-end的数字 在先序上第一个数字在中序的位置
    public static int getHeadIndex(int [] pre,int [] in,int begin,int end){
        int res  = -1;
        if (end - begin ==pre.length){
            return 0;
        }
        ArrayList<Integer> list= new ArrayList<>();
        for (int a= 0;a<=(end-begin);a++){
            list.add(in[begin+a]);
        }
        for (int b=0;b<pre.length;b++){
            if (list.contains(pre[b])){
                res = b;
                break;
            }
        }
        return res;
    }



    public static void printTree(TreeNode root){
        if (root==null){
            return;
        }
        printTree(root.left);
        System.out.println(root.val);
        printTree(root.right);
    }


}
